#ifndef LEETCODE_CN_CPP_PROBLEMS_148_H
#define LEETCODE_CN_CPP_PROBLEMS_148_H

#include "utils/list.h"

namespace problem_148
{

class Solution
{
private:
    ListNode *mergeSortedList(ListNode *l1, ListNode *l2)
    {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;
        ListNode tmpHead(0);
        auto pre = &tmpHead;
        while (l1 != nullptr || l2 != nullptr)
        {
            if (l1 != nullptr && l2 != nullptr)
            {
                if (l1->val < l2->val)
                {
                    pre->next = l1;
                    l1 = l1->next;
                }
                else
                {
                    pre->next = l2;
                    l2 = l2->next;
                }
            }
            else if (l1 != nullptr)
            {
                pre->next = l1;
                l1 = l1->next;
            }
            else
            {
                pre->next = l2;
                l2 = l2->next;
            }
            pre = pre->next;
        }
        return tmpHead.next;
    }

public:
    ListNode *sortList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        auto slow = head, fast = head->next;
        while (fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
            if (fast->next)
                fast = fast->next;
        }
        auto l1 = sortList(slow->next);
        slow->next = nullptr;
        auto l2 = sortList(head);
        return mergeSortedList(l1, l2);
    }
};

} // namespace problem_148

#endif //LEETCODE_CN_CPP_PROBLEMS_148_H
